import java.util.function.BinaryOperator;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 19182
 * Date: 2025-10-11
 * Time: 8:09
 */
public class AVLTree {
    static class TreeNode{
        public int val;
        public int bf; //平衡因子
        public TreeNode parent;
        public TreeNode left;
        public TreeNode right;
        public TreeNode(int val){
            this.val = val;
        }
    }
    public TreeNode root; //根节点

    public boolean insert(int val){
        TreeNode node = new TreeNode(val);
        if(root == null){
            root = node;
            return true;
        }
        //按二叉搜索树逻辑插入
        TreeNode parent = null;
        TreeNode cur = node;
        while(cur != null){
            if(cur.val < val){
                parent = cur;
                cur = cur.right;
            }else if(cur.val > val){
                parent = cur;
                cur = cur.left;
            }else{
                return false; //节点已经存在，不允许重复插入
            }
        }
        if(cur.val > val){
            parent.left = cur;
        }else{
            parent.right = cur;
        }
        node.parent = parent;
        cur = node;
        //更新平衡因子
        while(parent != null){  //最多更新到祖宗节点
            if(parent.left == cur){
                parent.bf--;
            }else{
                parent.bf++;
            }

            if(parent.bf == 0){ //
                break;
            }else if(parent.bf == 1 || parent.bf == -1){
                cur = parent;
                parent = cur.parent;
            }else{
                if(parent.bf == 2){ //右子树高了
                    if(cur.bf == 1){    //单纯的右子树高
                        RotateLeft(parent);
                    }else{
                        RotateRL(parent);
                    }
                }else{  //左子树高了
                    if(cur.bf == -1){   //单纯的左子树高
                        RotateRight(parent);
                    }else{
                        RotateLeft(parent);
                    }
                }
            }
        }
        return true;
    }
    private void RotateLeft(TreeNode parent){
        TreeNode subR = parent.right;
        TreeNode subRL = subR.left;

        parent.right = subRL;
        subR.left = parent;
        if(subRL != null){  //这里有可能为空
            subRL.parent = parent;
        }
        TreeNode pParent = parent.parent;
        parent.parent = subR;

        if(root == parent){ //如果是祖宗节点，那么subR作为祖宗节点
            root = subR;
            root.parent = null;
        }else{  //不是，判断parent是pParent的左节点还是右节点，把subR和pParent建立关系
            if(pParent.left == parent){
                pParent.left = subR;
            }else{
                pParent.right = subR;
            }
            subR.parent = pParent;
        }
        subR.bf = parent.bf = 0;
    }
    private void RotateRight(TreeNode parent){
        TreeNode subL = parent.left;
        TreeNode subLR = subL.right;

        parent.left = subLR;
        subL.right = parent;
        if(subLR != null){
            subLR.parent = parent;
        }
        TreeNode pParent = parent.parent;
        parent.parent = subL;

        if(root == parent){ //如果parent是祖宗节点， 那么上面肯定没有其他节点，直接把subL替换成祖宗节点即可
            root = subL;
            root.parent = null;
        }else{  //如果不是，判断parent是pParent的左节点还是右节点，把subL与pParent建立关系
            if(pParent.left == parent){
                pParent.left = subL;
            }else{
                pParent.right = subL;
            }
            subL.parent = pParent;
        }
        subL.bf = parent.bf = 0;
    }
    private void RotateRL(TreeNode parent){
        TreeNode subR = parent.right;
        TreeNode subRL = subR.left;
        int bf = subRL.bf;  //到底如何更新平衡因子，要分情况讨论这个子树的平衡因子
        RotateRight(parent.right);  //先右旋把他变成单纯的右子树高
        RotateLeft(parent);
        if(bf == 1){
            subRL.bf = 0;
            subR.bf = 0;
            parent.bf = -1;
        }else if(bf == -1){
            subRL.bf = 0;
            subR.bf = 1;
            parent.bf = 0;
        }
        //为0的情况不用讨论，RotateLeft和RotateRight已经把他设置0
    }
    private void RotateLR(TreeNode parent){
        TreeNode subL = parent.left;
        TreeNode subLR = subL.right;
        int bf = subLR.bf;
        RotateLeft(parent.left);
        RotateRight(parent);
        if(bf == -1){
            subLR.bf = 0;
            subL.bf = 0;
            parent.bf = 1;
        }else if(bf == 1){
            parent.bf = 0;
            subLR.bf = 0;
            subL.bf = -1;
        }
    }
    private void Inorder(TreeNode root){
        if(root == null){
            return;
        }
        Inorder(root.left);
        System.out.print(root.val + " ");
        Inorder(root.right);
    }
    private int height(TreeNode root){
        if(root == null){
            return 0;
        }
        int leftH = height(root.left);
        int rightH = height(root.right);
        return leftH > rightH ? leftH + 1 : rightH + 1;
    }
    private boolean isBalanced(TreeNode root){  //判断是不是AVL树，要是中序遍历有序(搜索树)，左右高度之差为1
        if(root == null){
            return true;
        }
        int leftH = height(root.left);
        int rightH = height(root.right);

        return Math.abs(leftH - rightH) <= 1 && isBalanced(root.left) && isBalanced(root.right);
    }
}
